852B - Neural Network country - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;

long long n,m,k;

const int mod=1e9+7;

int bb[N];

struct mar
{
	int n,m;
	long long num[105][105];
};

void init(mar &a)
{
	memset(a.num,0,sizeof(a.num));
	for(int i=0; i<=k; i++)
	{
		a.num[i][i]=1;
	}
	return;
}

void pt(mar a)
{
	for(int i=0; i<=k; i++)
	{
		for(int j=0; j<=k; j++)
		{
			cout<<a.num[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<"---------\n";
}


mar operator *(const mar &a,const mar &b)
{
	mar ans;
	memset(ans.num,0,sizeof(ans.num));
	ans.n=a.n;
	ans.m=b.m;
	for(int i=0; i<ans.n; i++)
	{
		for(int j=0; j<ans.m; j++)
		{
			for(int k=0; k<a.m; k++)
			{
//				if(i>j||i>k||j>k)continue; 
				ans.num[i][j]=(ans.num[i][j]+((a.num[i][k]*b.num[k][j])%mod))%mod;
			}
		}
	}
	return ans;
}

mar binpow(mar a,long long b)
{
	mar ans;
	ans.n=k;
	ans.m=k;
	init(ans);
	while(b>0)
	{
		if(b&1)
		{
			ans=ans*a;
		}
		a=a*a;
		b>>=1;
	}
	return ans;
}




void solve()
{
	cin>>n>>m>>k;
	mar a,b,c;
	a.n=k;
	a.m=k;
	b.n=k;
	b.m=k;
	c.n=k;
	c.m=k;
	for(int i=1; i<=n; i++)
	{
		int x;
		cin>>x;
		a.num[0][x%k]++;
	}
	for(int i=1; i<=n; i++)
	{
		int x;
		cin>>x;
		for(int j=0; j<k; j++)
		{
			b.num[j][(j+x)%k]++;
		}
		bb[i]=x;
	}
	for(int i=1; i<=n; i++)
	{
		int x;
		cin>>x;
		x+=bb[i];
		c.num[((k-x)+100*k)%k][0]++;
	}
//	pt(a);
//	pt(b);
//	pt(binpow(b,m-2));
	mar ans=a*binpow(b,m-2)*c;
//	pt(ans);
	cout<<ans.num[0][0]<<"\n";


}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tn=1;
//	cin>>tn;
	while(tn--)
	{
		solve();
	}
}